use std::cmp::{min, Ordering};
use std::ptr::{copy, copy_nonoverlapping, swap, write};

// ((2 << i + 1) -1 + 2 * (i % 2)) / 3
const INT: [usize; 15] = [
    1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845,
];

#[inline]
fn max_int(half: usize) -> usize {
    INT.iter().position(|x| *x > half + 1).unwrap()
}

unsafe fn merge_insert(x: &mut [i64]) {
    let (len, half) = (x.len(), x.len() / 2);
    if len > 2 {
        let mut large = vec![0i64; half];
        for i in (0..half).rev() {
            if x.get_unchecked(2 * i) > x.get_unchecked(2 * i + 1) {
                copy_nonoverlapping(&x[2 * i + 1], &mut x[i + half], 1);
                copy_nonoverlapping(&x[2 * i], &mut large[i], 1);
            } else {
                copy_nonoverlapping(&x[2 * i], &mut x[i + half], 1);
                copy_nonoverlapping(&x[2 * i + 1], &mut large[i], 1);
            }
        }
        merge_insert(&mut large);
        copy_nonoverlapping(&x[half], &mut x[0], 1);
        copy_nonoverlapping(large.as_ptr(), x.as_mut_ptr().add(1), half);

        let mut n = half;
        let end = max_int(half);
        for i in 1..end {
            let idx = min(len, half + INT[i]) - 1;
            while n < idx {
                let (mut p, mut q) = (0, n + 1);
                let val = x[idx];
                while p != q {
                    match x[(p + q) / 2].cmp(&val) {
                        Ordering::Less => p = (p + q) / 2 + 1,
                        Ordering::Greater => q = (p + q) / 2,
                        Ordering::Equal => break,
                    }
                }
                p = (p + q) / 2;
                copy(x.as_ptr().add(p), x.as_mut_ptr().add(p + 1), idx - p);
                write(&mut x[p], val);
                n += 1;
            }
        }
    } else if x.get_unchecked(0) > x.get_unchecked(1) {
        swap(&mut x[0], &mut x[1]);
    }
}

#[test]
fn insert() {
    let mut sequence = vec![41, 23, 5, 98, 117, 76, 59, 80, 120, 33, 144];
    unsafe { merge_insert(&mut sequence) };
    assert_eq!(vec![5, 23, 33, 41, 59, 76, 80, 98, 117, 120, 144], sequence);
}
